Решение: прибавление арифметической прогрессии по диагоналям, вертикали и горизонтали в офлайне, получим решение за O ( n m ) O(nm) .